/*
Merge Intervals Total Accepted: 41351 Total Submissions: 184212 My Submissions Question Solution
Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].


*/
#include <iostream>
#include "print.h"
#include <vector>
#include <algorithm>

using namespace std;


/***/
 //Definition for an interval.
struct Interval {
    int start;
    int end;
    Interval() : start(0), end(0) {}
    Interval(int s, int e) : start(s), end(e) {}
};

class Solution {
public:
	struct CompareFirst{
		CompareFirst(bool asce) :asce_(asce)
		{ }
		bool operator()(const Interval &left, const Interval &right)
		{
			return asce_ ? left.start <right.start : left.start > right.start;

		}
	private:
		bool asce_;

	};

	vector<Interval> merge(vector<Interval>& intervals) {
		int size = intervals.size();
		if (size <= 1)
		{
			return intervals;
		}

		vector<Interval> res;
		sort(intervals.begin(), intervals.end(), CompareFirst(true));
		res.push_back(intervals[0]);

		for (int i = 1; i < size; i++)
		{
			if (res[res.size()-1].end < intervals[i].start)
			{
				res.push_back(intervals[i]);
			}
			else
			{
				if (res[res.size() - 1].end < intervals[i].end)
				{
					res[res.size() - 1].end = intervals[i].end;
				}
			}

		}



		return res;
	}
};


int main()
{
	//int a[] = { 1, 1, 2 };
	vector<Interval> nums;
	Interval a2(1, 3), a1(2, 6), a3(8, 10), a4(15, 19);
	nums.push_back(a1);
	nums.push_back(a2);
	nums.push_back(a3);
	nums.push_back(a4);


	vector<Interval> res;
	Solution s;
	int n = 4;
	res = s.merge(nums);


	system("pause");
	return 0;
}